﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Arithmetic
{
    public class Select
    {
        /// <summary>
        /// 链表实现基数排序，需要知道最大的数
        /// </summary>
        /// <param name="array">源数组</param>
        /// <param name="places">最大数位数</param>
        /// <returns></returns>
        public static int[] RadixSort(int[] array, int places)
        {
            int mod = 10;int dev = 1;
            int arrayLength = array.Length;
            List<SingleLinkedList<int>> list=new List<SingleLinkedList<int>>();
            for (int i = 0; i < 10; i++)
            {
                list.Add(new SingleLinkedList<int>());
            }          
         
            List<int> intlist = new List<int>();

            for (int i = 0; i < places; i++, mod *= 10, dev *= 10)  //最大数的位数决定遍历的次数
            {
                for (int j = 0; j < array.Length; j++)   
                {
                    int temp = (array[j] % mod) / dev;   //选出各个位权的基数
                    list[temp].AddLast(new MyLLNode<int> { Value = array[j] });  //给0~9中的一个链表添加元素
                }

                for (int k = 0; k < 10; k++)
                {
                    for (int m = 0; m < list[k].GetLength(); m++)
                    {
                        intlist.Add(list[k][m]);
                    }
                    list[k].Clear();  //清空链表中的数据
                }                              
                array = intlist.ToArray();
                intlist.Clear();             
            }
            return array;
        }

        static void Main()
        {
            int[] array = new int[10] { 100000, 98564, 45896, 4589, 1000, 789, 568, 89, 42, 3 };
            int[] d=RadixSort(array,6);
            foreach (int g in d)
            {
                Console.Write(g+" ");
            }
            Console.ReadKey();
        }
    }

    class SingleLinkedList<T>
    {
        public MyLLNode<T> First
        {
            get;
            set;
        }

        public MyLLNode<T> Last
        {
            get;
            set;
        }

        public void AddLast(MyLLNode<T> node)
        {
            if (First == null)
            {
                First = node;
                Last = node;
                node.Next = null;
            }
            else
            {
                Last.Next = node;
                Last = Last.Next;//(Last=node;)
                Last.Next = null;
            }
        }

        public int GetLength()
        {
            if (First == null) return 0;
            MyLLNode<T> temp = First;
            int count = 1;
            while (true)
            {
                if (temp.Next != null)
                {
                    temp = temp.Next;
                    count++;
                }
                else break;
            }
            return count;
        }
        
        public T this[int index]
        {
            get
            {
                MyLLNode<T> temp = First;
                for (int i = 0; i < index; i++)
                {
                    temp = temp.Next;
                }
                return temp.Value;
            }
        }

        public void Clear()
        {
            First = null;
        }
    }

    class MyLLNode<T>
    {
        public T Value
        {
            get;
            set;
        }

        public MyLLNode<T> Next
        {
            get;
            set;
        }
    }
}
